DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2019.8

A Priori Search Space Pruning in the Flight Planning Problem

Authors: Adam Schienle, Pedro Maristany, and Marco Blanco

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract

We study the Flight Planning Problem for a single aircraft, where we look for a minimum cost path in the airway network, a directed graph. Arc evaluation, such as weather computation, is computationally expensive due to non-linear functions, but required for exactness. We propose several pruning methods to thin out the search space for Dijkstra’s algorithm before the query commences. We do so by using innate problem characteristics such as an aircraft’s tank capacity, lower and upper bounds on the total costs, and in particular, we present a method to reduce the search space even in the presence of regional crossing costs. We test all pruning methods on real-world instances, and show that incorporating crossing costs into the pruning process can reduce the number of nodes by 90% in our setting.

Cite as

Adam Schienle, Pedro Maristany, and Marco Blanco. A Priori Search Space Pruning in the Flight Planning Problem. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schienle_et_al:OASIcs.ATMOS.2019.8,
  author =	{Schienle, Adam and Maristany, Pedro and Blanco, Marco},
  title =	{{A Priori Search Space Pruning in the Flight Planning Problem}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{8:1--8:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.8},
  URN =		{urn:nbn:de:0030-drops-114205},
  doi =		{10.4230/OASIcs.ATMOS.2019.8},
  annote =	{Keywords: time-dependent shortest path problem, crossing costs, flight trajectory optimization, preprocessing, search space}
}

Search Results

Documents authored by Maristany, Pedro

A Priori Search Space Pruning in the Flight Planning Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message